\section{Ejercicio 5}

\subsection{Implentación del algoritmo Lottery Scheduler}

\paragraph{Implementación}
Una de las cosas mas sorprendentes del \textbf{Lottery Scheduler} es la simplicidad de su implementación. 
Todo lo que se necesita es una eficiente manera de generar numeros al azar (random numbers, distribuidos de manera uniforme) para
elegir el ticket ganador, una estructura de datos para realizar un seguimiento de los procesos del sistema (en nuestro caso usamos
un vector), y el número total de ticket (que en nuestro caso lo derivamos de la sumatoria de los tickets repartidos).

\paragraph{¿Cómo asignar Tickets?}
Un problema que nos encontramos fue: ¿Cómo asignar tickets?
Este problema es una pregunta difícil, porque, por supuesto, el comportamiento del sistema 
depende en gran medida de cómo se asignan los tickets. Un enfoque consiste en asignar la misma cantidad de 
tickets a todos los procesos de esta manera la probabilidad de que que salga uno es equanime. Otro enfoque consiste en asignar
tickets de forma aleatoria o en caso de que saber que tipo de tarea se esta corriendo priorizar según tipo de tarea. Como en 
principio no sabemos que tipo de tarea esta corriendo en el scheduler, decidimos asignar una cantidad de tickets fijos (1) para 
cada tarea que se carga en el scheduler.


Primero queremos aclarar que se decicidió que a cada tarea se le asigne 1 ticket y este número se incrementa a medida que
gane compensaciones por bloqueo. A partir de este momento, la tarea tiene más probabilidad de salir ganador en los próximos
sorteos. Cuando resulta ganador de la lotería, esta compensación se le es retirada volviendo a 1, cantidad inicial.
Decidimos omitir el hecho de que una tarea pueda subdividirse en threads, junto con el manejo de tickets del usuario. Con esto
queremos decir que al no existir usuarios (sólo uno) no existe la posibilidad del cambio de cantidad de tickets bajo un mismo
usuario.

\paragraph{Otras optimizaciones y refinamientos}

\begin{itemize}
 \item \textbf{Tickets Transfer}  \\
Con Transferencia de tickets, un proceso puede entregar temporalmente sus tickets a otro proceso. Esta capacidad es especialmente
útil en un entorno Cliente/Servidor, donde un proceso Cliente envía un mensaje a un servidor pidiéndole que hacer. Para acelerar
el trabajo, el cliente puede pasar los tickets al servidor y por lo tanto tratar de maximizar el rendimiento del servidor
mientras el servidor se encarga de la petición del cliente. Cuando haya terminado, el servidor transfiere los tickets de vuelta
al cliente y todo resulta como al principio.
Como lo único que implementamos es el scheduler no tenemos manera de implementar la interfaz para que dos procesos puedan 
transferir tickets, por tal motivo esta optimización no la implementamos.

 \item \textbf{Ticket inflation} \\
Con tickets inflation, un proceso puede aumentar o disminuir el número de tickets que posee temporalmente. 
Por supuesto, en un escenario de competencia con procesos que no confían entre sí, esto no tiene mucho sentido; 
un proceso codicioso podría asignarse un gran número de tickets y tomar toda la CPU. Tickets inflation se puede
aplicar en un entorno donde un grupo de procesos confian entre sí; en tal caso, si cualquier proceso sabe que 
necesita más tiempo de CPU, puede aumentar sus tickets como una manera de reflejar esa necesidad al sistema,
sin la necesidad de comunicarse con otros procesos.
Como en nuestro caso no sabemos si un proceso necesita o no más CPU decidimos no implementar ticket inflaction.

 \item \textbf{Ticket Currencies} \\
Tickets Currencies permite a un usuario con un conjunto de tickets asignar tickets entre sus propias tareas de la 
manera quiera. Entonces, el sistema convierte automáticamente dichos tickets en el valor global correcto.

Por ejemplo, asumiendo que el usuario A y B cada uno tienen 100 tickets:
El usuario A esta corriendo 2 tareas, $A_{1}$ y $A\_{2}$ y le asigno a cada uno 500 tickets (de 1000 en total) de su propios tickets.
El usuario B esta corriendo sólo una tarea y asigna 10 tickets (de 10 en total). El sistema convierte las asignaciones
de $A_{1}$ y $A_{2}$ de 500 cada una a 50 cada una en el sistema global de tickets; igualmente, para B 10 tickets serán convertidos a 100 tickets
El sorteo sera realizado sobre la cantidad global de tickets (200 en total) para determinar que tarea escojer.

\begin{tabbing}
Usuario A \= $\rightarrow$ \= 500 a \= $A_{1}$ $\rightarrow$ 50  \=  \= (global currency) \\
	  \> $\rightarrow$ \> 500 a \> $A_{2}$ $\rightarrow$ 50  \>  \> (global currency) \\
Usuario B \> $\rightarrow$ \> 10 a  \> $B_{1}$ $\rightarrow$ 100 \>  \> (global currency) \
\end{tabbing}

Decidimos omitir el hecho de que una tarea pueda subdividirse en threads, junto con el manejo de tickets del usua<rio. Con esto
queremos decir que al no existir usuarios (solo uno) no existe la posibilidad del cambio de cantidad de tickets bajo un mismo
usuario.

Por otro lado, el paper habla de que un ticket es activo mientras es utilizado por un proceso. Cuando un proceso es removido 
de la cola de listos, sus tickets son desactivados. Y son reactivados cuando vuelven a la cola de listos. Esto lo
implementamos cuando un proceso se bloquea, es decir si un proceso se bloquea sus tickets no se tienen en cuenta 
para el sorteo, recien cuando el proceso de desbloquea sus tickets se vuelven a tener en cuenta.
  
\end{itemize}

\paragraph{}
A continuación mostramos un pseudocódigo de la función $tick$ implementada. 

\begin{algorithmic}

\Function{tick}{int cpu, const enum Motivo m}
\Switch{$m$}
    \Case{$EXIT$}      
      \State $RemoveCurrentTask(cpu)$
      \State $taskToExecute\gets nextTask()$      
    \EndCase
    \Case{$TICK$}
      \If {$remainder == 0$}
	\State $remainder\gets quantum$
	\State $taskToExecute\gets nextTask()$	
      \Else
      	\State $remainder\gets remainder - 1$
      	\State $taskToExecute\gets current_pid(cpu)$	
      \EndIf 
    \EndCase
    \Case{$BLOCK$}
      \State $remainder\gets quantum$
      \State $block(current\_pid(cpu))$
      \State $doCompensation(current\_pid(cpu))$
      \State $taskToExecute\gets nextTask()$
    \EndCase
  \EndSwitch
  \State 
  \Return $taskToExecute$
\EndFunction
\end{algorithmic}

\paragraph{}
A continuación mostramos un pseudocódigo de la función $nextTask$ implementada. Esta función es la que realiza la implementación
del algoritmo de lottery

\begin{algorithmic}
\Function{nextTask}{}
  \For {\textit{Cada una de las tareas t que estan en la cola}}
    \If {\textit{la tarea t no esta bloqueada}}
      \State $tickets\_total\gets tickets\_total + tikets\_t$
    \EndIf
  \EndFor
  
  \State $winner\gets rand()\%total\_tickets-1$
  \State $summation\gets 0$
  \For {\textit{Cada una de las tarea t que estan en la cola}}
    \If {\textit{la tarea t no esta bloqueda}}
      \State $summation\gets summation + tikets\_t$
      \If {$summation > winner$}
	\State $task\_chosen\gets t$
      \EndIf
    \EndIf
  \EndFor
  
  \Return $task\_chosen$
   
\EndFunction    
\end{algorithmic}